package com.zjj.lbw.interview.stringSearch;

import java.util.Arrays;

/**
 * @author zhanglei.zjj
 * @description 字符串搜索之KMP算法
 * @date 2023/9/17 4:07
 */
public class KMP {
    static int search(char[] str, char[] pattern, int[] next) {
        int i = 0, j = 0;

        while (i < str.length && j < pattern.length) {
            if (j == -1 || str[i] == pattern[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j == pattern.length) {
            return i - j;
        } else {
            return -1;
        }
    }

    static void getNext(char[] pattern, int[] next) {
        // 初始值
        next[0] = -1;
        int i = 0, j = -1;

        while (i < pattern.length) {
            if (j == -1) {
                i++;
                j++;
            } else if (pattern[i] == pattern[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                // 程序执行到这里，是前面的某个后缀和前缀已经匹配上了部分字符，然后在j位置失配
                // 在算next数组时 本身也可以使用next数组，根据部分匹配表 快速移动
                // 也就是相当于 j之前位置已经匹配上，下次只用从j之后位置继续匹配
                j = next[j];
            }
        }
        System.out.println(Arrays.toString(next));
    }

    public static void main(String[] args) {
        String str1 = "ABCABCAABCABCD";
        String strPattern = "ABCABCD";
        int[] next = new int[strPattern.length()];
        getNext(strPattern.toCharArray(), next);

        int i = search(str1.toCharArray(), strPattern.toCharArray(), next);
        System.out.println(i);
    }
}
